package demo.practice.binary_tree;

import demo.practice.TreeNode;

import java.util.LinkedList;

public class P285 {

//    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
//
//
//    }


    public static void main(String[] args) {
        P285 p285 = new P285();
        TreeNode root = new TreeNode(2);
        TreeNode left = new TreeNode(1);
        TreeNode right = new TreeNode(3);

        root.left = left;
        root.right = right;

        TreeNode node = p285.inorderSuccessor(root, left);

    }

    LinkedList<TreeNode> queue;

    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        queue = new LinkedList<>();
        foreach(root);
        while (queue.size() > 0) {
            TreeNode cur = queue.poll();
            if (cur.val == p.val && queue.size() > 0)
                return queue.poll();
        }

        return null;
    }

    private void foreach(TreeNode root) {
        if (root == null)
            return;
        if (root.left != null)
            foreach(root.left);

        queue.add(root);

        if (root.right != null)
            foreach(root.right);
    }


}
